import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * 给你一个链表的头节点 head 和一个特定值 x
 * 对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
 * 需要保留 两个分区中每个节点的初始相对位置。
 * User: xwl
 */

class ListNode6 {
    int val;
    ListNode6 next;
    ListNode6() {}
    ListNode6(int val) { this.val = val; }
    ListNode6(int val, ListNode6 next) { this.val = val; this.next = next; }
}

public class Test8 {
    public ListNode6 partition(ListNode6 head, int x) {
        // 创建俩个新的链表，分别用来存储大于x的节点和小于x的节点
        ListNode6 bs = null;
        ListNode6 be = null;
        ListNode6 as = null;
        ListNode6 ae = null;
        // 定义一个节点指向当前节点
        ListNode6 cur = head;
        // 遍历
        while (cur != null) {
            // 插入节点
            if (cur.val < x) {
                // 初始情况
                if (bs == null) {
                    bs = cur;
                    be = cur;
                }else {
                    be.next = cur;
                    be = be.next;
                }
            }else {
                // 初始情况
                if (as == null) {
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            // cur后移
            cur = cur.next;
        }
        // 给尾节点的next置空
        if (as != null) {
            ae.next = null;
        }
        // 讨论当大于x和小于x的节点不同时存在的情况
        if (bs == null) {
            return as;
        }
        // 连接
        be.next = as ;
        // 返回
        return bs;
    }
}
